package cn.genmer.test.security.algorithm.sort;

import cn.genmer.test.security.algorithm.entity.IntExtend;

public class SelectSort {
    public static void main(String[] args) {
        int[] arr = {3, 0, 1, 2, 4};
        sort(arr);
        printArray(arr);
    }

    /**
     * 初始版本 - 找最小值，放前面，如此往复
     * @param arr
     */
    public static void sort(int[] arr){
        for (int i=0; i<arr.length-1; i++){
            int minpos = i;
            for (int j=i; j<arr.length; j++){
                minpos = arr[minpos] < arr[j] ? minpos : j;
            }
            swap(arr, minpos,i);
        }
    }

    /**
     * 优化版本 - 同时找最大最小，节省一半循环次数
     * @param arr
     */
    public static void sort2(int[] arr){
        int len = arr.length/2;
        int n = arr.length;
        for (int i=0; i<len; i++){
            int minpos = i;
            int maxpos = n-1;
            for (int j=i; j<n; j++){
                minpos = arr[minpos] < arr[j] ? minpos : j;
                maxpos = arr[maxpos] > arr[j] ? maxpos : j;
            }
            swap(arr, minpos,i);
            if (maxpos == i) maxpos = minpos;
            swap(arr, maxpos,n-1);

            n = n-1;
        }
    }
    /**
     * 验证稳定性版本
     * @param arr
     */
    public static void sort2(IntExtend[] arr){
        int len = arr.length/2;
        int n = arr.length;
        for (int i=0; i<len; i++){
            int minpos = i;
            int maxpos = n-1;
            for (int j=i; j<n; j++){
                minpos = arr[minpos].getValue() < arr[j].getValue() ? minpos : j;
                maxpos = arr[maxpos].getValue() > arr[j].getValue() ? maxpos : j;
            }
            swapExtent(arr, minpos,i);
            if (maxpos == i) maxpos = minpos;
            swapExtent(arr, maxpos,n-1);

            n = n-1;
        }
    }

    /**
     * 测试记忆版本
     * 【2022.11.20】【初始】 错， min放到循环外了 && j开始坐标定为了0
     *              【优化】错，问题在，最大下标交换位置 size-1写成了i
     *  【2022.11.20】【初始】 通过
     *               【优化】 通过， 卡在【内层循环控制错误】一段时间
     *  【2022.11.30】【初始】 通过
     *               【优化】 通过
     * @param arr
     */
    public static void sortTEST(int[] arr){
        int size = arr.length;
        for (int i = 0; i < size-1; i++) {
            int min = i;
            int max = size;
            int innerIndex = size;
            for (int j = i; j < innerIndex; j++) {
                if (arr[min] > arr[j]) min = j;
                if (arr[max] < arr[j]) max = j;
            }
            swap(arr, i, min);
            if (max == i) max = min;
            swap(arr, innerIndex-1, max);
        }
    }

    private static void swap(int[] arr, int pos1, int pos2){
        int temp = arr[pos1];
        arr[pos1] = arr[pos2];
        arr[pos2] = temp;
    }
    private static void swapExtent(IntExtend[] arr, int pos1, int pos2){
        IntExtend temp = arr[pos1];
        arr[pos1] = arr[pos2];
        arr[pos2] = temp;
    }
    public static void printArray(int [] arr){
        for (int i: arr){
            System.out.print(i + " ");
        }
        System.out.println();
    }
    public static void printArray(IntExtend [] arr){
        for (IntExtend i: arr){
            System.out.print(i.getIndex() + " ");
        }
    }
}
